const common = require('./base/common');
const TreeNode = require('./dataStruct/treeNode').TreeNode;

/**
 * 牛客网1. 先序 + 中序数组构建树
 * 
 * @param {*} pre 
 * @param {*} vin 
 */
let reConstructBinaryTree = function(pre, vin) {
    let root = null,
        curIndex = 0;
        stack = [{start: 0, end: vin.length, parent: null, isLeft: false}];

    if(pre.length != vin.length) {
        throw new Error("pre sequence != in sequence.");
    }

    while(stack.length > 0 && curIndex < pre.length) {
        let range = stack.pop(),
            cur = pre[curIndex++],
            pIndex = -1,
            node = new TreeNode(cur);
        
        // 找到先序遍历中的节点在中序遍历节点中的顺序
        for(let i=range.start; i < range.end; ++i) {
            if(vin[i] == cur) {
                pIndex = i;
                break;
            }
        }

        // 树的构建
        if(range.parent == null) {
            root = node;
        } else if(range.isLeft) {
            range.parent.lchild = node;
        } else {
            range.parent.rchild = node;
        }

        // 后构建右子树
        if(pIndex + 1 < range.end) {
            stack.push({start: pIndex + 1, end: range.end, parent: node, isLeft: false});
        }

        // 先构建左子树，放到栈顶
        if(range.start < pIndex) {
            stack.push({start: range.start, end: pIndex, parent: node, isLeft: true});
        }
    }

    return stack.length > 0? null: root;
}

common.testing([
    [[1,2,3,4,5,6,7,8], [1,3,5,7,8,6,4,2]],
    [[1,2,3,4,5,6,7,8], [2,4,6,8,7,5,3,1]],
    [[1,2,3,4,5,6,7,8], [1,2,3,4,5,6,7,8]],
    [[1,2,4,7,3,5,6,8], [4,7,2,1,5,3,8,6]],
    [[1,3,5,7,2,4,6,8], [8,6,4,2,7,5,3,1]],
    [[8,7,1,2,3,4,6,5], [4,3,2,1,7,8,5,6]]
])(x => reConstructBinaryTree(x[0], x[1]));